package _2022.hot100._215_数组中的第k个最大元素;

import java.util.Arrays;

/**
 * @author： YHSimon
 * @date： 2022-05-15 09:53
 */
public class Solution {
    public int findKthLargest3(int[] nums,int k){
        int len=nums.length;
        Arrays.sort(nums);
        return nums[len-k];
    }

    // 堆排序 大顶堆
    public int findKthLargest(int[] nums,int k){
        int heapSize=nums.length;
        buildMaxHeap(nums,heapSize);
        for(int i=nums.length-1;i>=nums.length-k+1;i--){
            swap(nums,0,i);
            heapSize--;
            maxHeapify(nums,0,heapSize);
        }
        return nums[0];
    }

    public void buildMaxHeap(int[] nums,int heapSize){
        for(int i=heapSize/2;i>=0;i--){
            maxHeapify(nums,i,heapSize);
        }
    }

    public void maxHeapify(int[] nums,int i,int heapSize){
        int l=i*2+1,r=i*2+2,largest=i;
        if(l<heapSize&&nums[l]>nums[largest]){
            largest=l;
        }
        if(r<heapSize&&nums[r]>nums[largest]){
            largest=r;
        }
        if(largest!=i){
            swap(nums,i,largest);
            maxHeapify(nums, largest, heapSize);
        }
    }

    public void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }



    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findKthLargest(new int[]{3,2,1,6,5,4}, 2));
    }
}
